1. Technical Field
The present invention relates processing trajectory data and, in particular, to determining whether a vertex is on a given path.
2. Description of the Related Art
Trajectory data can be collected in very large amounts as complex systems, such as road systems, are mapped and explored. Trajectory data may be represented as a graph, with vertices representing, e.g., intersections and arcs representing, e.g., roads. In such a graph, a path is represented as a sequence of consecutive vertices, and each edge in the path is defined as a pair of such vertices.
Determining whether a given vertex exists within a given path can be very resource intensive. Due to the potentially very large size of paths, even a linear search may take a long time to complete. Another conventional algorithm uses an inverted index, but such solutions have high memory costs. As a result, the conventional techniques for determining whether a vertex exists on a given path are inadequate for situations where rapid determinations or large datasets are used.